\section{Introduction}
\label{sec:introduction}
\noindent
Today, many control applications are implemented on distributed
embedded systems comprising multiple computation nodes that
communicate over a bus. Automotive and avionic applications are the
most prominent examples of such systems. The aggressive shrinking of
transistor sizes and the environmental factors of such systems makes
embedded electronic devices increasingly prone to
faults~\cite{borkar05}. Broadly, faults may be classified as transient
or permanent. Transient faults (e.g., caused by electromagnetic
interference) manifest themselves for a short time and then disappear
without causing permanent damage to devices.  Due to the feedback of
sensor measurements to the control loop, temporary performance
degradations caused by such faults are often automatically remedied in
the next sampling instants.  Thus, transient faults are typically
tolerated by control applications.  Permanent faults, however, sustain
for much longer time intervals, until diagnosed and repaired, or in
the worst case for the remaining lifetime of the system. Permanent
faults can occur due to aging, wear-out, design defects, or
manufacturing defects~\cite{korenFTbook}.  In case a computation node
fails due to a permanent fault, control applications that run tasks on
this node will potentially become unstable. To avoid such situations,
these tasks that were running on failed nodes must now be activated
and executed on other nodes. In addition to appropriate
fault-detection mechanisms~\cite{kopetz97}, the system must thus adapt
to situations in which nodes fail, as well as adapting and
reintegrating nodes when these are operational again.

In this paper, we propose a framework for fault-tolerant operation of
control applications in the presence of permanent faults. When a node
fails, the \textit{configuration} (i.e., the set of available nodes)
of the underlying distributed system changes. The tasks that were
running on the failed node must now be activated at other available
nodes of this new configuration.  To guarantee stability and some
level of control quality of the control applications, it is necessary
that a solution for this new configuration has been synthesized at
design time and that the system has the ability to adapt to this
solution at runtime.  A solution comprises a mapping, a schedule, and
controllers that must be optimized for the available computation nodes
in a certain configuration.  However, such a construction is not
trivial due to that the total number of configurations is exponential
in the number of nodes of a distributed system. Therefore, one cannot
afford to synthesize the mapping and schedules for all the
configurations in the design space.  We propose a method to synthesize
the mapping and schedule for a small number of configurations and
still provide guarantees on the fault-tolerant capabilities of the
system. Towards this, we present an algorithm to identify a set of
mandatory base configurations (Section~\ref{sec:base}). Given that the
designer specifies the minimum number of nodes that are always
available, our algorithm ensures that the base configurations are
sufficient to cover all fault scenarios that may arise.  Base
configurations provide a certain minimum level of control quality and
are typically few in number. To improve control quality, the designer
can thus afford to synthesize solutions for configurations other than
the base configurations. We present a technique
(Section~\ref{sec:dse}) to judiciously select additional
configurations for synthesis such that the control quality of the
system is further improved relative to the minimum quality level
provided by the base configurations. Task remapping and migration are
mechanisms that are used to adapt to different configurations at
runtime. These mechanisms and the solutions prepared by our framework
are sufficient to operate the system in case computation nodes
fail. The alternative to this software-based approach is hardware
replication, which can be very costly in some application domains; for
example, the design of many applications in the automotive domain are
highly cost constrained. Base configurations do not only provide
proper operation in presence of faults, but also constitute important
information to the designer as to whether or not hardware replication
of a certain node is needed.


Recently, there has been a lot of interest in design and optimization
of embedded control
systems~\cite{blind,seto01,cervincontroltiming}. The reported methods
focus on synthesis of the control law, as well as the execution and
communication schedule of the distributed system. However, the
proposed methods assume that the nodes operate without faults. There
has also been considerable interest in fault-tolerance techniques that
rely on task replication and remapping~\cite{PinelloCS08,Lee10}. These
works are significantly different as compared to our work. First, none
of them focused on control-quality optimization. Unlike our technique,
which guarantees that all fault scenarios are handled at runtime, the
methods consider a set of predefined fault scenarios. Finally, while
our proposed heuristic can judiciously select configurations from the
huge design space to improve control quality, no such approach has
been proposed before.

The remainder of this paper is organized as follows.  In the next
section, we present the system model and a corresponding
control-quality metric. In Section~\ref{sec:base}, we define base
configurations and demonstrate that it is necessary and sufficient to
support execution in such configurations in order to tolerate any
designer-specified fault.  We present a heuristic for further
optimization of control quality in Section~\ref{sec:dse}, and the
experimental evaluation in Section~\ref{sec:experiments}. Last, the
paper is concluded in Section~\ref{sec:conclusion}.



